Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

Solution:

  1. public class Solution {
  2.   public String largestNumber(int[] num) {
  3.     int n = num.length;
  5.     Integer[] A = new Integer[n];
  6.     for (int i = 0; i < n; i++) {
  7.       A[i] = Integer.valueOf(num[i]);
  8.     }
  10.     // sort the array by string
  11.     Arrays.sort(A, new Comparator<Integer>() {
  12.       @Override
  13.       public int compare(Integer a, Integer b) {
  14.         String stra = String.valueOf(a);
  15.         String strb = String.valueOf(b);
  17.         return (strb + stra).compareTo(stra + strb);
  18.       }
  19.     });
  21.     StringBuilder sb = new StringBuilder();
  23.     for (int i = 0; i < n; i++) {
  24.       if (A[i] == 0 && sb.length() == 0) {
  25.         continue;
  26.       }
  28.       sb.append(String.valueOf(A[i]));
  29.     }
  31.     if (sb.length() == 0) {
  32.       return "0";
  33.     }
  35.     return sb.toString();
  36.   }
  37. }